1. Field of the Invention
The present invention generally relates to secure key cryptography, and in particular to methods for distributing key material in a secure manner over a nonsecure network.
2. Background Description
Currently, there is no acceptable way to distribute key material over the commercial telecommunications network in a secure manner, without the separate distribution of a password, key, certificate or token (either through the mail, or a physical third party interaction). The network is nonsecure and subject to compromise by a skilled Interloper. The difficulty of secure communications under the prior art may be understood by reference to the following assumptions: (1) an Interloper on the network can intercept all communications between a Subscriber and a commercial Provider; (2) the Interloper has all the facilities of the Subscriber, but does not have the facilities of the Provider; (3) the Subscriber (hitherto unknown to the Provider) is responding to the Provider's solicitation, but has no material provided by the Provider; and (4) the Subscriber will attempt to set up a secure account on his first digital contact with the Provider using commercially available software (e.g., off-the-shelf web browser, etc.).
FIG. 1A shows a Provider of services and a potential Subscriber to those services connected to a nonsecure network in accordance with the foregoing assumptions. FIG. 1B shows message traffic when a potential Subscriber and a service Provider try to establish a session in the presence of an Interloper on the network.
A number of prior art solutions require the use of several open or "public" keys. An encryption method is said to be a public key encryption scheme when, for each associated encryption/decryption pair, one key (the public key) is made publicly available, while the other key (the private key) is kept secret. The following attributes characterize public key encryption: (i) keys are generated in pairs, consisting of a public key and a private key; (ii) there is always a mathematical relationship between the two keys, but this relationship is based on some "hard" problem (i.e. one that cannot be solved in a reasonable amount of time using any computer system currently available); (iii) the private key cannot be derived from its corresponding public key; and (iv) information encrypted in the public key can only be decrypted by its corresponding private key
There are several key patents and established protocols that are applicable and serve in their own ways as predecessors for the methods of passing electronic keys in accordance with the present invention, as will be described hereafter.
U.S. Pat. No. 3,962,539 to Ehrsam et al. sets forth the algorithm for generating block ciphers, outlining how key bits are used, regarding the nonlinear transformation within S-boxes, and regarding a particular permutation. The DES cipher, although an improvement on the preexisting cipher put forth in the Feistel patent (U.S. Pat. No. 3,798,359), does not address a protocol for secure transmission of a cipher key between two parties, via an electronic, real-time medium, where neither party has any a priori knowledge of the other.
U.S. Pat. No. 4,200,770 to Hellman et al. is the first public-key patent issued and offers a solution for communicating securely over a nonsecure channel without a priori shared keys. Security rests on the intractability of the Diffie-Hellman problem and the related problems of computing discrete logarithms. This method provides protection from passive adversaries (eavesdroppers), but not from active adversaries capable of intercepting, modifying, or injecting messages. The weaknesses in this system spring from neither party having any assurance of the source identity of incoming messages or the identity of the party which may know the resulting key, i.e., there is no entity authentication or key authentication. The general class of attacks that this solution is vulnerable to may be prevented by authenticating the exchanged exponentials, e.g., by a digital signature. A solution offered in a later derivation of the Diffie-Hellman patent by El Gamal relies upon a fixed public exponential of the recipient which has verifiable authenticity (e.g. is embedded in a certificate). This solution relies on a physical passing of the certificate from one party to the other by a trusted third party.
The RSA public-key encryption and signature system (described in U.S. Pat. No. 4,405,829 to Rivest et al.) outlines the current accepted state of the art for public-key technology. The RSA system represents practical application and derivations of the ideas set forth in the original Diffie-Hellman key agreement patent. Although the methods set forth in this patent provide adequate security for electronic communications, the problem of establishing initial secure electronic contact and transporting keys without a priori shared keys persists. The "hard" problem involved in encrypting and decrypting also places undesired strain on the average user equipped with a standard personal computer system of today's computational limitations.
Perhaps the most relevant example of prior art is a no-key protocol which is attributed to Shamir by Konheim [A. G. Konheim, Cryptography, A Primer, John Wiley and Sons, New York, 1981, p.345]. This protocol allows users A and B to transfer a secret key K with privacy, but no authentication, over a public channel within three passes. This is achieved by first publishing a prime number p chosen such that computation of discrete logarithms modulo p is infeasible. A and B then choose respective secret random numbers a,b and each performs parallel but separate computations of a.sup.-1 and b.sup.-1 mod p.sup.-1. A then chooses a random key K, computes Ka mod p and transports it to B. It is then modified exponentially by B, and then sent back to A, who effectively undoes its previous exponentiation and yields K as altered by B. A then sends back a message, containing the value of K.sup.b mod p to B, who exponentiates the value using his originally generated b.sup.-1 mod p.sup.-1, thus yielding the newly shared key K mod p.
Although this protocol does describe a method that theoretically passes a previously unknown key to a user, it has not been put into practical commercial use because of the impractical computational strain on the average user who would be in need of establishing an immediate secure communications link with a Provider.